package 算法shiyan.shiayn3;/**
 * ************************************************************************
 * 项目名称: projectweb <br>
 * 文件名称:  <br>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br>
 * 文件创建：1913040634刘世锦  <br>
 * 创建时间: 2021/4/10 <br>
 *
 * @version v1.0 <br>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br>
 * ************************************************************************
 */

/**
 * @ProjectName: projectweb
 * @ClassName: 归并排序
 * @Author: 1913040634刘世锦
 * @Date: 2021/4/10 20:34 .
 * @version v1.0
 */
public class 归并排序 {
    public static void main(String[] args) {
        int [] a = {8,7,2,3,5,16,4,8,36,13};
        mergesort(a,0,a.length-1);
        System.out.print("归并排序：[");
        for (int i:a) {
            System.out.print(i + " ");
        }
        System.out.println("]");
    }

        public static void mergesort(int [] a,int s,int e){
             if(s<e){
                 int m = (s+e)/2;
                 mergesort(a,s,m); //分解左边
                 mergesort(a,m+1,e); //分解右边
                 merge(a,s,m,e);   //合并

             }


    }
        public static void merge(int[] a,int s,int m,int e){

        int[] t = new int[e-s+1];
        int l = s;      //左半部分的起始位置
        int r = m+1;    //右半部分的起始位置
        int i = 0;      //存放的位置
        while (l<=m &&r<=e ){
            if(a[l]<=a[r]){
                t[i] = a[l];
                i++;l++;
            }else{
                t[i]  = a[r];
                i++;r++;
            }
        }
        while(l<=m){
            t[i] = a[l];
            i++;l++;
        }
            while(r<=e){
                t[i] = a[r];
                i++;r++;
            }

            for (int n = 0; n < t.length; n++) {
                a[s+n] = t[n];
            }

    }



    }
